/*
 * OrderedSet.h
 *
 *  Created on: 30/08/2012
 *      Author: marcio
 */

#ifndef ORDEREDSET_H_
#define ORDEREDSET_H_


/*!
 * \class OrderedSet
 * \brief A Set of elements with a pre-specified Order between then.
 *
 * This abstract class represents a abstract set of elements, with a pre-specified order between every
 * two elements of the universe(a total order).
 *
 * The universe of all the elements that can belong to the set is defined in each child class
 * that implements this abstract one. The total is defined in the child class as well.
 *
 * Observe that the elements must be the notion of equality. So for
 * this class work well with a data structure it has to overwritte the operator =,
 * the operator ==  and the operator !=.
 *
 * This class provide same methods to manipulate the set and to do same basic
 * set operations on the objects, but is highly recommended that all this methods be implemented
 * in the concretes classes that inherit from this one.
 *
 *	The template parameter especified the type of the elements in the universe set. Note that all
 *	The the elements of the universe are of the same type.
 *
 * \tparam T the type of each element in the universe.
 *
 * **/
template <typename T>
class OrderedSet{

protected:

	long n;//!< the number of elements in the universe.

	/*!
	 * \brief Copy Constructor.
	 *
	 * Constructor to be used to allocate memory to a object of this class.
	 */
	OrderedSet(){};

	/*!
	 * \brief Basic Constructor
	 *
	 * A simple constructor to a empty set in a universe of size elements all of type T.
	 *
	 * \param the number of elements in the universe.
	 * **/
	OrderedSet(long size){ n = size;};

public:


	/*! \class OrderedSet<T>::Iterator
	 * \brief A general iterator to a OrderedSet
	 *
	 * A general iterator to a OrderedSet. It visit each element in the set used
	 * to construct a object of this class.
	 *
	 * The elements will be visited according the total order especified over the
	 * elements of the universe. So each concrete child class must implement its
	 * own Iterator based in the order that each one have.
	 *
	 * An object of this class keeps the state of an enumeration. This means that
	 * various enumerations can be performed simultaneously provided that each of
	 * them is associated with a different iterator. But it is not possible to modify
	 * the set in the middle of a enumeration. If it happen a error will occur.
	 *
	 * **/
	class Iterator {
	public:

		/*!
		 * \brief The destructor.
		 *
		 * A simple destructor.
		 */
		virtual ~Iterator(){};

		/*!
		 * \brief Start the enumeration
		 *
		 * This method must be called before any call to hasnext() or next(). Otherwise a
		 * error will occur.
		 *
		 * This method start the enumeration of the first element in the set
		 *
		 */
		virtual void start() = 0;

		/*!
		 * \brief Restart the enumeration
		 *
		 * This method start the enumeration again. Beware that all the current state
		 * of the object will be lost and the enumeration will begin again from
		 * the first element in the set according to the order in the universe.
		 */
		virtual void restart() = 0;

		/*!
		 * \brief Restart the enumeration from a specified element
		 *
		 * This method start the enumeration again. Beware that all the current state
		 * of the object will be lost.
		 *
		 * The enumeration will begin again from the first element in the set bigger or
		 * equal to the specified element according to the order in the universe.
		 *
		 * \param i the specified element
		 */
		virtual void restartFrom(T i) = 0;

		/*!
		 * \brief Verify if the set has same element not enumerated yet.
		 *
		 * Look in the set if same element was not enumerated each. The
		 * enumeration is represent by the call to the method next(). if
		 * a element of the set was a element return by next(), it was enumerated
		 * , otherwise it was not.
		 *
		 * \return true if there is a element not enumerated in the set and false
		 * otherwise.
		 */
		virtual bool hasNext() = 0;

		/*!
		 * \brief Enumerate the elements in the set
		 *
		 * It will return the next element not visited yet by the Iterator.
		 *
		 * All the calls to next() must has done after a call to hasnext() and
		 * only must be care out if the hasnext() returns true.
		 *
		 * Try to call next() when there is no element in the set not enumerated each
		 * will case a error.
		 *
		 * \return the next element to be enumerate
		 */
		virtual T next() = 0;
	};

	/*!
	 * \brief Destructor
	 *
	 * A simple destructor to a object of this class
	 */
	virtual ~OrderedSet();

	/*!
	 * \brief Create a copy of this object
	 *
	 * This method must be implement in each concrete class that inherit from that one.
	 *
	 * \return a copy of this object
	 */
	virtual OrderedSet<T>* clone() = 0;

	/*!
	 * \brief A Iterator for the set represented by the object
	 *
	 * Return a iterator to enumerate all the elements of the universe belonging to
	 * this object
	 *
	 *
	 * \return a iterator to the set
	 */
	virtual OrderedSet<T>::Iterator* newSetIterator() = 0;

	/*!
	 * \brief A Iterator for the set represented by the object with a filter.
	 *
	 * Return a iterator to enumerate all the elements of the universe belonging to
	 * the set represented by this object and the filter specified as a parameter.
	 *
	 * \param filter the speccified filter for the enumeration.
	 *
	 * \return a iterator to the set
	 */
	virtual OrderedSet<T>::Iterator* newSetIterator(OrderedSet<T>* filter) = 0;

	/*!
	 * \brief A Iterator for the complement of the set represented by the object
	 *
	 * Return a iterator to enumerate all the elements of the universe not belonging to
	 * this object
	 *
	 *
	 * \return a iterator to the complement of the set
	 */
	virtual OrderedSet<T>::Iterator* newComplIterator() = 0;

	/*!
	 * \brief A Iterator for the complement represented by the object with a filter.
	 *
	 * Return a iterator to enumerate all the elements of the universe belonging to
	 * the complement represented by this object and the filter specified as a parameter.
	 *
	 * \param filter the speccified filter for the enumeration.
	 *
	 * \return a iterator to the complement
	 */
	virtual OrderedSet<T>::Iterator* newComplIterator(OrderedSet<T>* filter) = 0;

	/*!
	 * \brief The smallest element bigger or equal to the element i in the set
	 *
	 * Return the smallest element, according the total order implemented over the universe,
	 * bigger or equal to the specified element that belongs to the set
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 *
	 * \param i the specified element
	 *
	 * \return the smallest element in the set bigger or equal to i
	 */
	virtual T nextSetElement(T i) = 0;

	/*!
	 * \brief The smallest element bigger or equal to the element i in the complement
	 *
	 * Return the smallest element, according the total order implemented over the universe,
	 * bigger or equal to the specified element that belongs to the complement of the set
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 *
	 * \param i the specified element
	 *
	 * \return the smallest element in the complement bigger or equal to i
	 */
	virtual T nextComplElement(T i) = 0;

	/*!
	 * \brief Add the specified element to the set.
	 *
	 * Add the element i to the set represented by the object.
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 *
	 * \param i the specified element.
	 *
	 */
	virtual void toSet(T i) = 0;

	/*!
	 * \brief Remove the specified element of the set.
	 *
	 * Remove the element i from the set represented by the object.
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 * \param i the specified element.
	 *
	 */
	virtual void toCompl(T i) = 0;

	/*!
	 * \brief Swap a element between the set and the complement.
	 *
	 * If the specified element is in the set it will be removed, if not
	 * it will be added.
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 *
	 * \param i the especified element.
	 *
	 */
	virtual void swapElement(T i);

	/*!
	 * \brief Verify if a element of the universe is in the set.
	 *
	 * Verify if the specified element belong or not to the set.
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 *
	 * \param i the specified element
	 *
	 * \return true if i belongs to the set and false otherwise
	 */
	virtual bool isInSet(T i) = 0;

	/*!
	 * \brief Verify if a element of the universe is in the complement.
	 *
	 * Verify if the specified element belong or not to the complement.
	 *
	 * The parameter i must be a element of the universe, otherwise a error will occur.
	 *
	 * \param i the specified element
	 *
	 * \return true if i not belong to the set and false otherwise
	 */
	virtual bool isInCompl(T i) = 0;

	/*!
	 * \brief Create a vector of the elements in the set
	 *
	 * Creates a vector with the size of the set in which each position
	 * is a element of the set represented by the object.
	 *
	 * The elements are stored respecting the total order between than, so
	 * if vec is the vector returned by this method, if i < j then
	 * vec[i] is smaller than vec[j].
	 *
	 * the parameter size will be overwrite to store the size of the set, so
	 * its previous value will be lost.
	 *
	 * \param size a pointer to store the size of the set.
	 *
	 * \return a array contains all the elements of the set.
	 */
	virtual T* toArray(long* size) = 0;

	/*!
	 * \brief The size of the universe
	 *
	 * This method will return the size of the universe in which this set is embedded.
	 *
	 * \return the size of the universe
	 */
	virtual long size();

	/*!
	 * \brief Verify if the set is empty
	 *
	 * Tests if the set was no elements. If the set was no elements it is empty
	 * and this method should return true.
	 *
	 * As this method depends on the data structure and the universe used, it has to be
	 * implemented in each child concrete class.
	 *
	 * \return true if the set is empty and false otherwise.
	 */
	virtual bool isEmpty() = 0;

	/*!
	 * \brief Add all the elements in the universe to the set
	 *
	 * Add all the elements in the universe to the set represented by this object
	 */
	virtual void allToSet() = 0;

	/*!
	 * \brief Add all the elements in the universe to the complement
	 *
	 * Add all the elements in the universe to the complement of the set represented by this object
	 */
	virtual void allToCompl() = 0;

	/*!
	 * \brief The complement of the current set
	 *
	 * Overwrite this object with its complement set.
	 *
	 * More precisely, be A is a set, then \f$\bar{A}\f$ is the complement of A if \f$x \in \bar{A}\f$
	 * if and only if \f$ x \notin A\f$.
	 *
	 */
	virtual void setComplement() = 0;

	/*!
	 * \brief The complement of the current set, stored in the set res
	 *
	 * This method has the same setComplement(), but do not overwrite the object.
	 *
	 * \param res the object to store the complement of the current set
	 * \see setComplement()
	 */
	virtual void setComplement(OrderedSet<T> * res) = 0;

	/*!
	 * \brief Union between the current set and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \in A\f$ or \f$x \in B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void setUnionSet(OrderedSet<T> * v);

	/*!
	 * \brief Simetric Difference between the current set and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \in A\f$ and \f$x \notin B\f$ or \f$x \notin A\f$ and \f$x \in B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void setDiffSimetricSet(OrderedSet<T> * v);

	/*!
	 * \brief Intersection between the current set and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \in A\f$ and \f$x \in B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void setIntersecSet(OrderedSet<T> * v);

	/*!
	 * \brief Difference between the current set and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \in A\f$ and \f$x \notin B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void setDiffSet(OrderedSet<T> * v);

	/*!
	 * \brief Union between the current set and the set represented by the object v
	 *
	 * This method has the same semantic of setUnionSet() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see setUnionSet()
	 */
	virtual void setUnionSet(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief SimetricDifference between the current set and the set represented by the object v
	 *
	 * This method has the same semantic of setDiffSimetricSet() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see setDiffSimetricSet()
	 */
	virtual void setDiffSimetricSet(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Intersection between the current set and the set represented by the object v
	 *
	 * This method has the same semantic of setIntersecSet() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see setIntersecSet()
	 */
	virtual void setIntersecSet(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Difference between the current set and the set represented by the object v
	 *
	 * This method has the same semantic of setDiffSet() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see setDiffSet()
	 */
	virtual void setDiffSet(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Union between the current complement and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \notin A\f$ or \f$x \in B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void complUnionSet(OrderedSet<T> * v);

	/*!
	 * \brief Simetric Difference between the current complement and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \notin A\f$ or \f$x \notin B\f$ or \f$x \in A\f$ or \f$x \in B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void complDiffSimetricSet(OrderedSet<T> * v);

	/*!
	 * \brief Intersection between the current complement and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \notin A\f$ and \f$x \in B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void complIntersecSet(OrderedSet<T> * v);

	/*!
	 * \brief Difference between the current complement and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \notin A\f$ and \f$x \notin B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void complDiffSet(OrderedSet<T> * v);

	/*!
	 * \brief Union between the current complement and the set represented by the object v
	 *
	 * This method has the same semantic of complUnionSet() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see complunionSet()
	 */
	virtual void complUnionSet(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Simetric Difference between the current set and the set represented by the object v
	 *
	 * This method has the same semantic of complDiffSimetricSet() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see complDiffSimetricSet()
	 */
	virtual void complDiffSimetricSet(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Intersection between the current complement and the set represented by the object v
	 *
	 * This method has the same semantic of complIntersecSet() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see complIntersecSet()
	 */
	virtual void complIntersecSet(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Difference between the current complement and the set represented by the object v
	 *
	 * This method has the same semantic of complDiffSet() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see complDiffSet()
	 */
	virtual void complDiffSet(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Union between the current set and the complement of the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \in A\f$ or \f$x \notin B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void setUnionCompl(OrderedSet<T> * v);

	/*!
	 * \brief Simetric Difference between the current set and the complement of the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \in A\f$ and \f$x \in B\f$ or \f$x \notin A\f$ or \f$x \notin B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void setDiffSimetricCompl(OrderedSet<T> * v);

	/*!
	 * \brief Intersection between the current set and the complement of the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \in A\f$ or \f$x \notin B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void setIntersecCompl(OrderedSet<T> * v);

	/*!
	 * \brief Difference between the current set and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \in A\f$ and \f$x \in B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void setDiffCompl(OrderedSet<T> * v);

	/*!
	 * \brief Union between the current set and the complemnet of the set represented by the object v
	 *
	 * This method has the same semantic of setUnionCompl() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see setUnionCompl()
	 */
	virtual void setUnionCompl(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Simetric Difference between the current set and the complemnet of the set represented by the object v
	 *
	 * This method has the same semantic of setDiffSimetricCompl() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see setDiffSimetricCompl()
	 */
	virtual void setDiffSimetricCompl(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Intersect between the current set and the complemnet of the set represented by the object v
	 *
	 * This method has the same semantic of setItersecCompl() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see setIntersecCompl()
	 */
	virtual void setIntersecCompl(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Diffence between the current set and the complemnet of the set represented by the object v
	 *
	 * This method has the same semantic of setDiffCompl() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see setDiffCompl()
	 */
	virtual void setDiffCompl(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Union between the current complement and the compplement of the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \notin C\f$ if and only if \f$x \notin A\f$ or \f$x \notin B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void complUnionCompl(OrderedSet<T> * v);

	/*!
	 * \brief Simetric Difference between the current complement and the complement of the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \notin A\f$ and \f$x \in B\f$ or \f$x \in A\f$ and \f$x \notin B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void complDiffSimetricCompl(OrderedSet<T> * v);

	/*!
	 * \brief Intersection between the current complement and the complement of the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \notin A\f$ or \f$x \notin B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void complIntersecCompl(OrderedSet<T> * v);

	/*!
	 * \brief Difference between the current set and the set represented by the object v
	 *
	 * This method overwrite the caller object with the result
	 *
	 * Let *A* be the set represented by the current object and *B* the set represented
	 * by the object v. This method produce as result the set C such that
	 * \f$ x \in C\f$ if and only if \f$x \notin A\f$ or \f$x \in B\f$
	 *
	 * \param v the other set to be operated
	 */
	virtual void complDiffCompl(OrderedSet<T> * v);

	/*!
	 * \brief Union between the current complement and the complement of the set represented by the object v
	 *
	 * This method has the same semantic of complUnionCompl() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see complUnionCompl()
	 */
	virtual void complUnionCompl(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Simetric Difference between the current complement and the complement of the set represented by the object v
	 *
	 * This method has the same semantic of complDiffSimetricCompl() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see complDiffSimetricCompl()
	 */
	virtual void complDiffSimetricCompl(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief intersect between the current complement and the complement of the set represented by the object v
	 *
	 * This method has the same semantic of complIntersecCompl() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see complIntersecCompl()
	 */
	virtual void complIntersecCompl(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Difference between the current complement and the complement of the set represented by the object v
	 *
	 * This method has the same semantic of complDiffCompl() but do not overwrite the caller
	 * object. The result of the operation is stored in the object passed as a
	 * parameter
	 *
	 * \param v the other set to be operated
	 * \param res the set to store the result of the operation
	 *
	 * \see complDiffCompl()
	 */
	virtual void complDiffCompl(OrderedSet<T> * v, OrderedSet<T> * res);

	/*!
	 * \brief Determine the first element of the set represented by the current object.
	 *
	 * Determine the first element of the set represented by the current object, according by the
	 * total order implemented by the element.
	 *
	 * If the set is empty the return will depend on the implementation on the concrete subclass.
	 *
	 * \return the first element in the set according to the total order.
	 */
	virtual T firstInSet() = 0;

	/*!
	 * \brief Determine the first element of the complement of the set represented by the current object.
	 *
	 * Determine the first element of the complement of the set represented by the current object, according by the
	 * total order implemented by the element.
	 *
	 * If the set is the whole universe the return will depend on the implementation on the concrete subclass.
	 *
	 * \return the first element in the set according to the total order.
	 */
	virtual T firstInCompl() = 0;

	/*!
	 * \brief The cardinality of the set represented by the object.
	 *
	 * The cardinality of the set represented by the set. The cardinality of the set is a
	 * natural number that counts the number of elements in it.
	 *
	 * \return the size of the current set.
	 */
	virtual long cardOfSet();

	/*!
	 * \brief The cardinality of the complement of the set represented by the object.
	 *
	 * The cardinality of the set represented by the set. The cardinality of the set is a
	 * natural number that counts the number of elements in it.
	 *
	 * \return the size of the complement of the current set.
	 */
	virtual long cardOfCompl();

};

template<typename T>
inline OrderedSet<T>::~OrderedSet(){}


template<typename T>
inline void OrderedSet<T>::swapElement(T i){
	if(isInSet(i))toCompl(i);
	else toSet(i);
}

template<typename T>
inline long OrderedSet<T>::size(){
	return n;
}

template<typename T>
inline void OrderedSet<T>::setUnionSet(OrderedSet<T> * v){
	Iterator* it = v->newSetIterator();
	while(it->hasNext())
		toSet(it->next());
}

template<typename T>
inline void OrderedSet<T>::setDiffSimetricSet(OrderedSet<T> * v){
	Iterator* it = v->newSetIterator();
	while(it->hasNext())
		swapElement(it->next());
}

template<typename T>
inline void OrderedSet<T>::setIntersecSet(OrderedSet<T> * v){
	Iterator* it = newSetIterator();
	T elem;
	while(it->hasNext()){
		elem = it->next();
		if(v->isInCompl(elem)) toCompl(elem);
	}
}

template<typename T>
inline void OrderedSet<T>::setDiffSet(OrderedSet<T> * v){
	Iterator* it = v->newSetIterator();
	while(it->hasNext())
		toCompl(it->next());
}

template<typename T>
inline void OrderedSet<T>::setUnionSet(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newSetIterator();
	while(it->hasNext())
		res->toSet(it->next());

	res->setUnionSet(v);
}

template<typename T>
inline void OrderedSet<T>::setDiffSimetricSet(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newSetIterator();
	while(it->hasNext())
		res->toSet(it->next());

	res->setDiffSimetricSet(v);
}

template<typename T>
inline void OrderedSet<T>::setIntersecSet(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newSetIterator();
	while(it->hasNext())
		res->toSet(it->next());

	res->setIntersecSet(v);
}

template<typename T>
inline void OrderedSet<T>::setDiffSet(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newSetIterator();
	while(it->hasNext())
		res->toSet(it->next());

	res->setDiffSet(v);
}

template<typename T>
inline void OrderedSet<T>::complUnionSet(OrderedSet<T> * v){
	setComplement();
	setUnionSet(v);
}

template<typename T>
inline void OrderedSet<T>::complDiffSimetricSet(OrderedSet<T> * v){
	setComplement();
	setDiffSimetricSet(v);
}

template<typename T>
inline void OrderedSet<T>::complIntersecSet(OrderedSet<T> * v){
	setComplement();
	setIntersecSet(v);
}

template<typename T>
inline void OrderedSet<T>::complDiffSet(OrderedSet<T> * v){
	setComplement();
	setDiffSet(v);
}

template<typename T>
inline void OrderedSet<T>::complUnionSet(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();
	Iterator* itv = v->newSetIterator();
	while(it->hasNext())
		res->toSet(it->next());

	while(itv->hasNext())
		res->toSet(itv->next());
}

template<typename T>
inline void OrderedSet<T>::complDiffSimetricSet(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();
	Iterator* itv = v->newSetIterator();
	while(it->hasNext())
		res->toSet(it->next());

	while(itv->hasNext())
		res->swapElement(itv->next());
}

template<typename T>
inline void OrderedSet<T>::complIntersecSet(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();
	while(it->hasNext()){
		T elem = it->next();
		if(v->isInSet(elem))res->toSet(elem);
	}
}

template<typename T>
inline void OrderedSet<T>::complDiffSet(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();
	T elem;
	while(it->hasNext()){
		elem = it->next();
		if(v->isInCompl(elem))res->toSet(elem);
	}
}

template<typename T>
inline void OrderedSet<T>::setUnionCompl(OrderedSet<T> * v){
	Iterator* itv = v->newComplIterator();

	while(itv->hasNext())
		toSet(itv->next());
}

template<typename T>
inline void OrderedSet<T>::setDiffSimetricCompl(OrderedSet<T> * v){
	Iterator* itv = v->newComplIterator();

	while(itv->hasNext())
		swapElement(itv->next());
}

template<typename T>
inline void OrderedSet<T>::setIntersecCompl(OrderedSet<T> * v){
	Iterator* it = newSetIterator();

	T elem;
	while(it->hasNext()){
		elem = it->next();
		if(v->isInCompl(elem))toCompl(elem);
	}
}

template<typename T>
inline void OrderedSet<T>::setDiffCompl(OrderedSet<T> * v){
	Iterator* it = newSetIterator();

	T elem;
	while(it->hasNext()){
		elem = it->next();
		if(v->isInSet(elem))toCompl(elem);
	}
}

template<typename T>
inline void OrderedSet<T>::setUnionCompl(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newSetIterator();
	Iterator* itv = v->newComplIterator();
	while(it->hasNext())
		res->toSet(it->next());

	while(itv->hasNext())
		res->toSet(itv->next());
}

template<typename T>
inline void OrderedSet<T>::setDiffSimetricCompl(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newSetIterator();
	Iterator* itv = v->newComplIterator();
	while(it->hasNext())
		res->toSet(it->next());

	while(itv->hasNext())
		res->swapElement(itv->next());
}

template<typename T>
inline void OrderedSet<T>::setIntersecCompl(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();

	T elem;
	while(it->hasNext()){
		elem = it->next();
		if(v->isInCompl(elem))res->toSet(elem);
	}
}

template<typename T>
inline void OrderedSet<T>::setDiffCompl(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();

	T elem;
	while(it->hasNext()){
		elem = it->next();
		if(v->isInSet(elem))res->toSet(elem);
	}

}

template<typename T>
inline void OrderedSet<T>::complUnionCompl(OrderedSet<T> * v){
	setComplement();
	setUnionCompl(v);
}

template<typename T>
inline void OrderedSet<T>::complDiffSimetricCompl(OrderedSet<T> * v){
	setComplement();
	setDiffSimetricCompl(v);
}

template<typename T>
inline void OrderedSet<T>::complIntersecCompl(OrderedSet<T> * v){
	setComplement();
	setIntersecCompl(v);
}

template<typename T>
inline void OrderedSet<T>::complDiffCompl(OrderedSet<T> * v){
	setComplement();
	setDiffCompl(v);
}

template<typename T>
inline void OrderedSet<T>::complUnionCompl(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();
	Iterator* itv = v->newComplIterator();
	while(it->hasNext())
		res->toSet(it->next());

	while(itv->hasNext())
		res->toSet(itv->next());
}

template<typename T>
inline void OrderedSet<T>::complDiffSimetricCompl(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();
	Iterator* itv = v->newComplIterator();
	while(it->hasNext())
		res->toSet(it->next());

	while(itv->hasNext())
		res->swapElement(itv->next());
}

template<typename T>
inline void OrderedSet<T>::complIntersecCompl(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();

	T elem;
	while(it->hasNext()){
		elem = it->next();
		if(v->isInCompl(elem))res->toSet(elem);
	}
}

template<typename T>
inline void OrderedSet<T>::complDiffCompl(OrderedSet<T> * v, OrderedSet<T> * res){
	Iterator* it = newComplIterator();

	T elem;
	while(it->hasNext()){
		elem = it->next();
		if(v->isInSet(elem))res->toSet(elem);
	}
}

template<typename T>
inline long OrderedSet<T>::cardOfSet(){
	Iterator* it = newSetIterator();
	long count = 0;
	while(it->hasNext())count++;
}

template<typename T>
inline long OrderedSet<T>::cardOfCompl(){
	Iterator* it = newComplIterator();
	long count = 0;
	while(it->hasNext())count++;
}

template<typename T>
class OrderedSetFactory{
public:
	virtual OrderedSet<T>* newOrderedSet(long n) = 0;

	virtual OrderedSet<T>* newOrderedSet(long n, void* handle) = 0;
};

#endif /* ORDEREDSET_H_ */
